package cn.itcast.com.RBT;

/**
 * Created by 郭浩 on 2020/8/25 10:00
 */
public class RedBlackTree<K extends Comparable<K>,V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;



    private TreeNode root;
    class TreeNode{
        //红黑树中结点的key
        K key;
        //结点的value
        V value;
        //红黑树结点的左右子树
        TreeNode left, right;
        //红黑树中结点的颜色
        boolean color;
        //记录该结点作为根节点的树中的所有元素个数
        int size;

        public TreeNode(K key, V value, TreeNode left, TreeNode right, boolean color, int size) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
            this.size = size;
        }
    }
    //在红黑树中，根据key，查找某个key对应的value，和普通的二叉搜索树没有区别
    public V get(K k){
        if (root == null){
            throw new RuntimeException("tree is null");
        }
        if (k == null){
            throw new IllegalArgumentException("param is null");
        }
        TreeNode x = root;
        while(x != null){
            int com = k.compareTo(x.key);
            if (com > 0) {
                x = x.right;
            }else if (com < 0){
                x = x.left;
            }else {
                return x.value;
            }
        }
        return null;
    }

    public TreeNode rotationLeft(TreeNode h){
        //交换位置
        TreeNode x = h.right;
        h.right = x.left;
        x.left = h;

        //改变颜色
        x.color = h.color;
        h.color = RED;

        //旋转之后。新点登顶
        x.size = h.size;
        h.size = h.left.size + h.right.size + 1;
        return x;
    }
    public TreeNode rotationRight(TreeNode h){
        //交换位置
        TreeNode x = h.left;
        h.left = x.right;
        x.right = h;

        //改变颜色
        x.color = h.color;
        h.color = RED;

        //旋转之后。新点登顶
        x.size = h.size;
        h.size = h.left.size + h.right.size + 1;
        return x;
    }

    //该方法是用来分裂结点的，，234树中间结点上移分裂，在红黑树上体现：分裂上去的结点和
    //别的上层结点构成一个结点，所以上一个结点要变成红色
    private TreeNode colorFlip(TreeNode x){
        x.color = !x.color;
        x.left.color = !x.left.color;
        x.right.color = !x.right.color;
        return x;
    }

    private TreeNode insert(TreeNode root,K key, V value){
        if (root == null){
            return new TreeNode(key,value,null,null,RED,1);
        }
        //判断左右结点是不是红色的,
        //如果是红色的，说明对应234树的4结点，需要向上分裂
        if (isRed(root.left) && isRed(root.right)){
            colorFlip(root);
        }
        int com = key.compareTo(root.key);
        if (com > 0){
            root.right = insert(root.right,key,value);
        }else if (com < 0){
            root.left = insert(root.left,key,value);
        }else {
            //新插入的元素在表中右相同的key
            root.value = value;
        }

        if (isRed(root.right)){
            root = rotationLeft(root);
        }
        if (isRed(root.left) && isRed(root.left.left)){
            root = rotationRight(root);
        }
        return root;
    }

    //判断某个结点是否为红色
    private boolean isRed(TreeNode right) {
        if (root == null){
            return false;
        }
        return root.color == RED;
    }
}





























































































































































































